// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem1047.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=1047 lang=cpp
 *
 * [1047] 删除字符串中的所有相邻重复项
 */

// @lc code=start
class Solution {
public:

    /*
    string removeDuplicates(string S) {
        int n = S.size();
        for(int i = 0 ; i < n - 1 ; i++)
        {
            if(S[i] == S[i + 1])
            {
                S.erase(i,2);
                return removeDuplicates(S);
            }
        }
        return S;
    }
    */
    string removeDuplicates(string S) {
        int n = S.size();
        string stk;
        for(int i = 0 ; i < n ; i++)
        {
            if(!stk.empty() && stk.back() == S[i])
            {
                stk.pop_back();
            }else
            {
                stk.push_back(S[i]);
            }
        }
        return stk;
        
    }
};
// @lc code=end

